C++ 数据结构与算法实战

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 反转链表
ListNode* Reverse(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 检测环（快慢指针）
bool HasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

// 找中间节点
ListNode* FindMiddle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// 合并两个有序链表
ListNode* MergeSorted(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (l1 && l2) {
        if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; }
        else { tail->next = l2; l2 = l2->next; }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 前序遍历（递归）
void Preorder(TreeNode* root, std::vector<int>& res) {
    if (!root) return;
    res.push_back(root->val);
    Preorder(root->left, res);
    Preorder(root->right, res);
}

// 层序遍历（BFS）
std::vector<std::vector<int>> LevelOrder(TreeNode* root) {
    std::vector<std::vector<int>> res;
    if (!root) return res;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        std::vector<int> level;
        for (int i = 0; i < size; ++i) {
            auto node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
    }
    return res;
}

// 最大深度
int MaxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + std::max(MaxDepth(root->left), MaxDepth(root->right));
}

// 判断是否对称
bool IsSymmetric(TreeNode* l, TreeNode* r) {
    if (!l && !r) return true;
    if (!l || !r) return false;
    return l->val == r->val
        && IsSymmetric(l->left, r->right)
        && IsSymmetric(l->right, r->left);
}

// 邻接表
std::vector<std::vector<int>> adj(n);
adj[u].push_back(v);   // u → v

// 带权邻接表
std::vector<std::vector<std::pair<int, int>>> adj(n);
adj[u].push_back({v, weight});

// BFS
std::vector<int> BFS(int start, const std::vector<std::vector<int>>& adj) {
    int n = adj.size();
    std::vector<int> dist(n, -1);
    std::queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

// DFS
std::vector<bool> visited;
void DFS(int u, const std::vector<std::vector<int>>& adj) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) DFS(v, adj);
    }
}

// 标准二分：查找目标值
int BinarySearch(const std::vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// 左边界二分：第一个 >= target 的位置
int LowerBound(const std::vector<int>& nums, int target) {
    int lo = 0, hi = nums.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 右边界二分：第一个 > target 的位置
int UpperBound(const std::vector<int>& nums, int target) {
    int lo = 0, hi = nums.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 有序数组两数之和
std::pair<int, int> TwoSum(const std::vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        if (sum == target) return {lo, hi};
        else if (sum < target) ++lo;
        else --hi;
    }
    return {-1, -1};
}

// 移除重复元素（原地）
int RemoveDuplicates(std::vector<int>& nums) {
    if (nums.empty()) return 0;
    int slow = 0;
    for (int fast = 1; fast < (int)nums.size(); ++fast) {
        if (nums[fast] != nums[slow]) {
            nums[++slow] = nums[fast];
        }
    }
    return slow + 1;
}

// 最长无重复子串
int LongestSubstring(const std::string& s) {
    std::unordered_set<char> window;
    int left = 0, maxLen = 0;
    for (int right = 0; right < (int)s.size(); ++right) {
        while (window.count(s[right])) {
            window.erase(s[left++]);
        }
        window.insert(s[right]);
        maxLen = std::max(maxLen, right - left + 1);
    }
    return maxLen;
}

// 滑动窗口模板
int SlidingWindow(const std::string& s, const std::string& t) {
    std::unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0, valid = 0;
    int result = INT_MAX;

    while (right < (int)s.size()) {
        char c = s[right++];
        // 窗口扩大时更新 window
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }
        // 判断是否需要收缩
        while (valid == (int)need.size()) {
            result = std::min(result, right - left);
            char d = s[left++];
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
        }
    }
    return result;
}

// 全排列
void Permute(std::vector<int>& nums, int start,
             std::vector<std::vector<int>>& res) {
    if (start == (int)nums.size()) {
        res.push_back(nums);
        return;
    }
    for (int i = start; i < (int)nums.size(); ++i) {
        std::swap(nums[start], nums[i]);
        Permute(nums, start + 1, res);
        std::swap(nums[start], nums[i]);  // 回溯
    }
}

// 组合（C(n,k)）
void Combine(int n, int k, int start,
             std::vector<int>& path, std::vector<std::vector<int>>& res) {
    if ((int)path.size() == k) {
        res.push_back(path);
        return;
    }
    for (int i = start; i <= n - (k - path.size()) + 1; ++i) {  // 剪枝
        path.push_back(i);
        Combine(n, k, i + 1, path, res);
        path.pop_back();  // 回溯
    }
}

// 0-1 背包
int Knapsack(const std::vector<int>& weights,
             const std::vector<int>& values, int capacity) {
    int n = weights.size();
    std::vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int w = capacity; w >= weights[i]; --w) {  // 逆序
            dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

// 最长递增子序列（LIS）
int LIS(const std::vector<int>& nums) {
    std::vector<int> tails;  // tails[i] = 长度为 i+1 的 LIS 末尾最小值
    for (int x : nums) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();  // O(n log n)
}

// 编辑距离
int EditDistance(const std::string& s, const std::string& t) {
    int m = s.size(), n = t.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));
    for (int i = 0; i <= m; ++i) dp[i][0] = i;
    for (int j = 0; j <= n; ++j) dp[0][j] = j;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = 1 + std::min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
        }
    }
    return dp[m][n];
}

// 下一个更大元素
std::vector<int> NextGreater(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> res(n, -1);
    std::stack<int> stk;  // 存索引，维护递减栈
    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && nums[stk.top()] < nums[i]) {
            res[stk.top()] = nums[i];
            stk.pop();
        }
        stk.push(i);
    }
    return res;
}

// 滑动窗口最大值（单调队列）
std::vector<int> MaxSlidingWindow(const std::vector<int>& nums, int k) {
    std::deque<int> dq;  // 存索引，维护递减队列
    std::vector<int> res;
    for (int i = 0; i < (int)nums.size(); ++i) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) res.push_back(nums[dq.front()]);
    }
    return res;
}

class UnionFind {
    std::vector<int> parent_, rank_;
public:
    explicit UnionFind(int n) : parent_(n), rank_(n, 0) {
        std::iota(parent_.begin(), parent_.end(), 0);
    }

    int Find(int x) {
        if (parent_[x] != x) parent_[x] = Find(parent_[x]);  // 路径压缩
        return parent_[x];
    }

    void Unite(int x, int y) {
        int px = Find(x), py = Find(y);
        if (px == py) return;
        if (rank_[px] < rank_[py]) std::swap(px, py);  // 按秩合并
        parent_[py] = px;
        if (rank_[px] == rank_[py]) rank_[px]++;
    }

    bool Connected(int x, int y) { return Find(x) == Find(y); }
};

class Trie {
    struct Node {
        std::array<std::unique_ptr<Node>, 26> children;
        bool is_end = false;
    };
    std::unique_ptr<Node> root_ = std::make_unique<Node>();

public:
    void Insert(const std::string& word) {
        Node* cur = root_.get();
        for (char c : word) {
            int idx = c - 'a';
            if (!cur->children[idx]) cur->children[idx] = std::make_unique<Node>();
            cur = cur->children[idx].get();
        }
        cur->is_end = true;
    }

    bool Search(const std::string& word) {
        Node* cur = root_.get();
        for (char c : word) {
            int idx = c - 'a';
            if (!cur->children[idx]) return false;
            cur = cur->children[idx].get();
        }
        return cur->is_end;
    }

    bool StartsWith(const std::string& prefix) {
        Node* cur = root_.get();
        for (char c : prefix) {
            int idx = c - 'a';
            if (!cur->children[idx]) return false;
            cur = cur->children[idx].get();
        }
        return true;
    }
};

class LRUCache {
    int capacity_;
    std::list<std::pair<int, int>> list_;  // {key, value}
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map_;

public:
    explicit LRUCache(int capacity) : capacity_(capacity) {}

    int Get(int key) {
        auto it = map_.find(key);
        if (it == map_.end()) return -1;
        list_.splice(list_.begin(), list_, it->second);  // 移到头部
        return it->second->second;
    }

    void Put(int key, int value) {
        if (auto it = map_.find(key); it != map_.end()) {
            it->second->second = value;
            list_.splice(list_.begin(), list_, it->second);
            return;
        }
        if ((int)list_.size() >= capacity_) {
            map_.erase(list_.back().first);
            list_.pop_back();
        }
        list_.emplace_front(key, value);
        map_[key] = list_.begin();
    }
};